1. The Field of the Invention
The present invention relates generally to multiply and divide circuits. More specifically, the present invention relates to a circuit that may either multiply or divide by interactively shifting and adding using a single arithmetic logic unit.
2. The Relevant Technology
Digital technology had transformed our world, and has led to such complex digital structures as high speed computers and digital communications networks. However, regardless of how complex the digital structure is, the structure relies on the processing of binary values. An example of such processing is multiplying and dividing through the use of binary multiplier and divider circuits.
Multiplication and division can be done in a variety of ways. For example, binary multiplication may be accomplished iteratively. On the first iteration, one bit of the multiplier would be multiplied by the entire multiplicand, and then shifted by an appropriate degree of magnitude of the multiplier bit to generate an initial product. Other products may be generated by multiplying (one at a time) the other multiplier bits by the entire multiplicand. In the interactive process, these intermediate products may be added cumulatively, until after all iterations are complete, the final product is generated.
Binary division may also be accomplished iteratively. On the first iteration, the divisor is divided into the entire dividend and a one is placed in the quotient. The divisor is then subtracted from the dividend. On the next iteration, the divisor is divided into the difference from the first iteration. If the divisor is larger than the difference, the dividend is shifted to the right one bit and a zero is added to the right end of the quotient. The shifting iterations takes place, with an accompanying zero being added to the right end of the quotient, until the difference plus the shift values are larger than the divisor. At that point a one is added to the right end of the quotient and the divisor is again subtracted from the dividend. In the interactive process, the shifting and subtracting repeats until the remaining bits in the dividend are less than the divisor. The final quotient will be the combination of ones and zeros with the remainder being the bits left over from the dividend.
Because multiplication and division of binary numbers includes adding and subtracting, the sign of the binary numbers is important. This has led to the development of signed and unsigned formats for representing binary values. Unsigned formats may be used to represent non-negative numbers. For example, the following table shows how three bits may be used to represent 8 different non-negative numbers (assuming that the binary point is to the right of the least significant bit):
TABLE 1Unsigned ExampleBinaryBase TenNumberValueInterpretation of bits00000x2{circumflex over ( )}2 + 0 * 2{circumflex over ( )}1 + 0 * 2{circumflex over ( )}000110x2{circumflex over ( )}2 + 0 * 2{circumflex over ( )}1 + 1 * 2{circumflex over ( )}001020x2{circumflex over ( )}2 + 1 * 2{circumflex over ( )}1 + 0 * 2{circumflex over ( )}001130x2{circumflex over ( )}2 + 1 * 2{circumflex over ( )}1 + 1 * 2{circumflex over ( )}010041x2{circumflex over ( )}2 + 0 * 2{circumflex over ( )}1 + 0 * 2{circumflex over ( )}010151x2{circumflex over ( )}2 + 0 * 2{circumflex over ( )}1 + 1 * 2{circumflex over ( )}011061x2{circumflex over ( )}2 + 1 * 2{circumflex over ( )}1 + 0 * 2{circumflex over ( )}011171x2{circumflex over ( )}2 + 1 * 2{circumflex over ( )}1 + 1 * 2{circumflex over ( )}0In this example, the each binary one bit contributes 2^n to the total value, where “n” represents the position of the bit in the sequence with 0 being the right-most bit.
A common way of representing signed binary values is referred to as “twos-complement”. In twos complement format, each positive bit contributes the same as each position would in the unsigned format just described, with one exception. The left-most and most significant bit contributes a negative value to the total sum. The following shows how three bits in twos complement format may represent numbers from −3 to 4 (assuming that the binary point is to the right of the least significant bit):
TABLE 2Signed ExampleBinaryBase TenNumberValueInterpretation of bits00000x2{circumflex over ( )}−2 + 0 * 2 {circumflex over ( )}1 + 0 * 2{circumflex over ( )}000110x2{circumflex over ( )}−2 + 0 * 2 {circumflex over ( )}1 + 1 * 2{circumflex over ( )}001020x2{circumflex over ( )}−2 + 1 * 2 {circumflex over ( )}1 + 0 * 2{circumflex over ( )}001130x2{circumflex over ( )}−2 + 1 * 2 {circumflex over ( )}1 + 1 * 2{circumflex over ( )}0100−41x2{circumflex over ( )}−2 + 0 * 2 {circumflex over ( )}1 + 0 * 2{circumflex over ( )}0101−31x2{circumflex over ( )}−2 + 0 * 2 {circumflex over ( )}1 + 1 * 2{circumflex over ( )}0110−21x2{circumflex over ( )}−2 + 1 * 2 {circumflex over ( )}1 + 0 * 2{circumflex over ( )}0111−11x2{circumflex over ( )}−2 + 1 * 2 {circumflex over ( )}1 + 1 * 2{circumflex over ( )}0
Many multiply or divide circuits are only configured to do either a multiply or a divide operation. In addition, many multiply or divide circuits cannot handle both unsigned and signed values simultaneously. Often the solution to this has been to implement more than one multiply or divide circuit. However, this may be costly and an inefficient use of space.
Therefore, what would be advantageous is a multiply and divide circuit with the flexibility to do both multiply and divide operations on both signed and unsigned binary numbers while minimizing hardware space.